package 最长重复子数组;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/17 11:13
 * @description:
 * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
 * 示例：
 * 输入：
 * A: [1,2,3,2,1]
 * B: [3,2,1,4,7]
 * 输出：3
 * 解释：长度最长的公共子数组是 [3, 2, 1] 。
 * 提示：
 * 1 <= len(A), len(B) <= 1000
 * 0 <= A[i], B[i] < 100
 */
public class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        // 子序列问题可以使用动态规划解决
        // ① dp数组及其下标含义：dp[i][j]表示nums1中以索引 i 结尾，nums2中以索引 j 结尾的最长子数字长度
        // ② 状态转移方程：nums[i] = nums[j] ? dp[i][j] = dp[i-1][j-1] + 1 : 0
        // ③ dp数组的初始化： nums1[0] == nums2[j] ? dp[0][j] = 1 : 0; nums1[i] == nums2[0] ? dp[i][0] = 1 : 0;
        // ④ 遍历顺序：从左上角遍历到右下角
        // ⑤ 举例推导dp数组：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
        //              index       0   1   2   3   4
        //                          0   0   1   0   0
        //                          0   1   0   2   0
        //                          1   0   0   0   3
        //                          0   0   0   0   0
        //                          0   0   0   0   0

        // 使用滑动数组
        int[] dp = new int[nums1.length];
        // 初始化第一个字符状态
        dp[0] = 0;
        int result = 0;

        // 先遍历 nums2
        for (int i = 0; i < nums2.length; i++) {
            // 再遍历 nums1
            for (int j = nums1.length - 1; j >= 1; j--) {
                if (nums2[i] == nums1[j]) {
                    dp[j] = dp[j - 1] + 1;
                } else {
                    dp[j] = 0;
                }
                // 更新结果
                result = Math.max(dp[j], result);
            }
            // 初始化第一个字符状态
            if (nums2[i] == nums1[0]) {
                dp[0] = 1;
            } else {
                dp[0] = 0;
            }
            // 更新结果
            result = Math.max(dp[0], result);
            System.out.println(Arrays.toString(dp));
        }
        return result;
    }
}
